package zuosheng.day3;

/**
 * @author lj
 * @Description: 桶-有序数组的相邻元素的最大差值
 * @date 2020-11-02 16:29
 * @QQ 851477108
 */


public class MaxGap {
    public static void main(String[] args) {
        int[] arr = {8,6,4,5,55,88,77,44,35,48,54};
        System.out.println(maxGap(arr));
    }

    public static int maxGap(int[] arr){
        if (arr == null || arr.length < 2){
            return 0;
        }

        int len = arr.length;
        //MAX_VALUE是int类型的最大值2^31-1，MIN_VALUE是int类型的最小值-2^31-1
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        //找到数组最小值和最大值
        for (int i = 0; i < len; i++) {
            min = Math.min(min, arr[i]);
            max = Math.max(max, arr[i]);
        }
        //如果最小值为最大值，没有意义
        if (min == max){
            return 0;
        }

        //关于桶的三个信息,桶的大小是len+1:[0,len];
        //false为空桶，true代表非空桶
        boolean[] hasNum = new boolean[len + 1];
        //maxs为桶的最大值的集合
        int[] maxs = new int[len + 1];
        //mins为桶的最小值的集合
        int[] mins = new int[len + 1];

        //桶id
        int bid = 0;
//遍历数组.将数组中每个数组与对应桶中位置上的数据比对,更新桶中最大值或最小值
        for (int i = 0; i < len; i++) {
            bid = bucket(arr[i], len, min, max);
            //当前hasNum[bid]为true,非空桶，需要比较最小值和当前的数值，得到最小值
            //当前hasNum[bid]为false,空桶，不需要比较，得到就是最小值，同时也是最大值
            mins[bid] = hasNum[bid] ? Math.min(mins[bid],arr[i]) : arr[i];
            maxs[bid] = hasNum[bid] ? Math.max(maxs[bid],arr[i]) : arr[i];
            //当前如果是空桶，则变为非空桶，非空桶不改变
            hasNum[bid] = true;
        }

        //最大差值
        int res = 0;
        //前桶的最大值
        int lastMax = maxs[0];
        int i = 1;
        //找一个非空桶及离它最近的非空桶，后桶的最小值减去前桶的最大值，找出最大差值
        for (; i < len; i++) {
            if (hasNum[i]){
                //比较前面的差值和当前的差值
                res = Math.max(res, mins[i] - lastMax);
                lastMax = maxs[i];
            }
        }
        return res;
    }

    //计算当前数应该去几号桶
    public static int bucket(long num, long len, long min, long max){
        //num所在的区域(num - min)
        //总区域(max - min)
        //区域的总大小len
        //区域的num大小len*(num - min)/(max - min)就是该桶的位置id
        return (int) (len*(num - min)/(max - min));

    }
}
